//#define  _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>
//
//int arr[9], book[9], n;
//
//void dfs(int step);
//
//int main()
//{
//	scanf("%d", &n);
//	dfs(0);
//	return 0;
//}
//
//void dfs(int step)
//{
//	if (step == n)
//	{
//		for (int i = 0; i < n; i++)
//		{
//			printf("%d", arr[i]);
//		}
//		printf("\n");
//		return;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		if (book[i] == 1)
//		{
//			continue;
//		}
//		arr[step] = i;
//		book[i] = 1;
//		dfs(step + 1);
//		book[i] = 0;
//	}
//	return;
//}